package Leetcode.每日一题;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName 重排链表
 * @since: 2023/7/31 10:06
 * @auth: kirito
 * @description:
 **/
public class 重排链表 {
    ListNode cur, prev;
    public void reorderList1(ListNode head) {
        reorderList(head, head);
    }
    public void reorderList(ListNode slow, ListNode fast) {
        if (fast == null) { //处理链表长度为偶数的情况
            cur = slow; //需要插入的第一个节点的前一个节点
            prev = null;
            return;
        }
        if (fast.next == null) { //处理链表长度为奇数的情况
            cur = slow.next; //需要插入的第一个节点
            slow.next = null;
            prev = slow; //重排后的最后一个节点
            return;
        }
        reorderList(slow.next, fast.next.next);
        ListNode next = cur.next;
        //节点交换
        slow.next = cur;
        cur.next = prev;
        prev = slow;
        cur = next;
    }


 public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

    public static void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int i = 0, j = list.size()-1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}
